Error correcting codes (ECCs) may be used to detect and in some cases correct errors introduced into data. Data may be corrupted during transmission and/or storage of the data to imperfect media. One frequently used ECC is a block code in which each block of data is protected by an ECC value generated from the block of data. Following transmission and/or storage of the block of data together with the ECC value, the block of data may be checked by an ECC check to detect corruption of the data. Certain detected errors may be corrected by using the ECC.
Data corruption by a typical transmission and/or storage media may generally be limited to a small portion of a block of data, such as a single bit of the data. An ECC check may determine from the block of data and the corresponding ECC value that the data is correct, the data has a single bit or other small amount of corruption that may be identified for correction, or that the data has corruption that cannot be corrected.
One class of ECC is a cyclic redundancy check (CRC) such as CRC-CCITT. In certain applications, CRC is used to detect corruption of large blocks of data without the possibility of correcting any detected corruption. CRC may also be used in other applications to detect errors and correct certain errors in smaller blocks of data. For example, CRC-CCITT may be used to detect many errors in blocks of data with 16 bits and to correct single bit errors detected in the 16-bit block of data.
Many ECCs were initially developed for relatively low-speed serial data communication and have efficient implementations using linear feedback shift registers for error detection and correction. Many data communication applications, including high-speed serial data communication, have data rates that exceed the processing rate possible using linear feedback shift registers. Circuits are needed that can detect and/or correct corruption of data at data rates that exceed the processing rate possible using linear feedback shift registers. In addition, circuits are needed that reduce the amount of logic necessary to detect and/or correct corruption of data at these high data rates.
The present invention may address one or more of the above issues.